Various methods and systems for vehicular navigation are well known. Particularly, many vehicle navigation systems rely on sensors to determine where a vehicle is positioned within an area of navigability. These systems typically employ a well understood technique known as dead-reckoning. Dead-reckoning is used to track the relative position of a vehicle with regard to another position, such as an origin. Typically, distance traversed and azimuth, or heading, are used to determine incremental changes in vehicular position with respect to the origin. These sensory systems inherently have error associated with their operation. A portion of this error is cumulative. This cumulative error detracts from the accuracy of the dead-reckoning navigation process. As a result of this inaccuracy, the actual vehicle position will not agree with the dead-reckoning vehicle position. This inaccuracy will likely increase, or continue to accumulate with additional distance traversed, thereby increasing the dead-reckoning error, or increasing the vehicle position uncertainty.
Several prior art systems have improved the accuracy of these dead-reckoning systems by matching the dead-reckoning position to a position associated with a location on a map. This is commonly known as map-matching. When the dead-reckoning behavior indicates that the vehicle is on the map, the dead-reckoning position may be adjusted to an absolute position, relative to this map thereby eliminating the cumulative error until the next map-matching step.
FIG. 1 illustrates the result of one of the simple, well known, map-matching techniques. A vehicle 101 starts at a known position 103 on a road segment 105. A dead-reckoning positioning system, associated with the vehicle 101, is initialized to that known position 103. A position reference is used to establish this known initial position 103, and typically may be a map or other absolute reference apparatus. This initialization step has an inherent inaccuracy, or uncertainty, bound by a position envelope, represented by reference number 107. This uncertainty may include the inaccuracy of the map, or other position reference, and a width of the road segment 105. The width of the road segment 105 is included because the vehicle 101 may be anywhere on the road segment 105. Of course, this particular position envelope 107 is one of many approximations of the actual geometry of the area of position uncertainty associated with the initial position reference. Here, an ellipse is used for convenience because it is a simple and often used representation of position envelopes.
When the vehicle 101 traverses, either off-road, or along the road segment 105, this position envelope 107 will increase in area, or uncertainty, as shown by reference number 107'. This increase in uncertainty is directly related to the cumulative sensor error described earlier. As a result, the dead-reckoning vehicle position may drift off of the mapped road segment as shown by reference number 101'. Reference number 109 shows the length of the position envelope 107', and reference number 111 shows the width of the position envelope 107'. Both the-length 109 and the width 111, and the orientation of these, will be a function of the initial uncertainty and the accumulated uncertainty that results from the vehicle sensor inaccuracies.
As the dead-reckoning position diverges too far from the position associated with the road segment 105, prior art systems will correct the dead-reckoning system by aligning per se. its position envelope 107' to the mapped road segment 105. If the vehicle 101 is traversing, without turning, on a singular road segment, the width, or position, uncertainty, generally resulting from heading associated with reference number 111 can be corrected by this action. If the vehicle turns then the length, or distance, uncertainty associated with reference number 109 can be corrected by associating the turn with a map topology. Corresponding to the same turn, the width, or heading uncertainty, may also be corrected. For a singular road segment a width, or heading, correction map-matching step is shown by reference numbers 101", 103', and 107" respectively. For clarity this is shown after a distance has been traversed along the road segment 105. In practice this uncertainty correction, or map-matching, is done at about one second intervals, and therefore the vehicle 101" is actually positioned more relatively dose to the vehicle 101'. Although this type of map-matching, for correcting position uncertainty, can be effective for this simple case, there are many types of road segment topologies that this simple scheme can be rendered hopelessly ineffective.
FIG. 2 shows a simple case of such a road segment topology. In this case a road segment 205 commences as a singular road segment, then road segment 209 diverges from road segment 205. Prior art map-matching schemes may consider this subtle branching of road segments as a singular road segment if the position envelope at least partially encompasses both road segments 205 and 209, due to a relatively large position uncertainty. In this case, the vehicle position is ambiguous because the road segment 205, 209 positions are ambiguous relative to the position envelope 207'. When this situation occurs, in prior art schemes, no map-matching update, or correction of cumulative position uncertainty is made in fear of making the wrong correction, thereby matching the vehicle 201 to the wrong road segment. While the vehicle 201 continues along this ambiguous set of road segments 205, 209 the sensor error will continue to accumulate and the uncertainty portion of the position envelope will continue to grow unbounded. Because of this, the vehicle may get lost as the position envelope accumulates to such a degree that it encompasses many road segments, making map matching unlikely from a practical and timely perspective.
Referring back to FIG. 2, it's easy to see the position envelope 207" growing unbounded, thereby getting out of control.
What is needed is an improved accuracy vehicle positioning method for optimizing the position envelope's size, corresponding to an increasing degree of uncertainty caused by sensors associated with a vehicle navigation system while an ambiguous road segment topology is present.